1. Field of the Invention
The present invention relates a method for planning or provisioning data transport networks, in particular optical networks employing wavelength division multiplexing (WDM).
2. Description of the Related Art
Transport networks are wide area networks that provide connectivity for aggregated traffic streams. Modern transport networks increasingly employ wavelength division multiplexing (WDM) technology to utilize the vast transmission bandwidth of optical fiber. WDM is based on transmission of data over separate wavelength channels on each fiber. Presently, WDM is mainly employed as a “point-to-point transmission technology”. In such networks, optical signals on each wavelength are converted to electrical signals at each network node. On the other hand, a “WDM optical networking technology”, which has been developed within the last decade, and which is becoming commercially available, employs wavelengths on an end-to-end basis, without electrical conversion in the network.
Planning of a transport network refers to assigning network resources to a traffic demand. Efficient planning is essential in minimizing the investment made on the network required to accommodate a given demand. In WDM networks, traffic is carried by means of circuit switched connections, optically routed on the basis of their wavelength. In the context of WDM optical networks, planning means routing and wavelength selection for a set of end-to-end wavelength allocation demands (or “connection requests”), given a demand distribution and a network structure.
A WDM network is characterized by its physical topology, that is, by the manner in which its nodes are interconnected by optical links. Though the ring is the most studied and most common topology today, mesh networks are being developed and are beginning to be deployed.
FIG. 1 shows an example of a mesh network 100 to which planning methods may be applied. There, a set of switching nodes 101 is interconnected by a plurality of fiber links 102 to form a network. It is assumed that each path p between any pair of source and destination nodes (not necessarily adjacent) requires a dedicated wavelength w on each link belonging to the path itself. The pair (p, w) will be referred as “lightpath”, w being a vector collecting the wavelengths w used on each link of the path. If the path p links adjacent nodes the lightpath is typically referred as “lighthop”. A source-destination node pair may require more than one lightpath. The typical context assumes that there is a fixed set of wavelengths available on each fiber, and therefore the connections are established at the expense of possibly multiple fibers on network links, typically bound in one or more optical cables. The switching nodes are the Optical Cross Connects (OXCs). They perform switching on the WDM transit lightpaths, preferably in all-optical way, that is, without intervention of electronics. In addition they may behave as terminal equipment for some lightpaths, performing add and/or drop functions. Further to switching, OXCs may effectuate wavelength conversion. In the context of planning, the term “wavelength”may refer to a label assigned to a lightpath in each link, instead of the actual value of the wavelength itself. Each fiber has a cost, typically reflecting the installed fiber material, optical amplifiers, and optical termination equipment at both ends of the link. The cost of the OXCs may also be taken into account. The objective of planning is typically taken as the minimization of the total network cost.
In WDM networks, routing is coupled with wavelength assignment, that is, which wavelength channel must be allocated to a lightpath in each link. The combination of these two functions is called Routing and Wavelength Assignment (RWA). In the case of multifiber links, RWA becomes Routing, Fiber and Wavelength Assignment (RFWA), as also a particular fiber must be selected on each link for a given lightpath. The complexity of the RFWA function greatly depends on the wavelength conversion capability of the switching nodes of the network. WDM networks may be distinguished in three categories, according to their wavelength conversion capability:                a) Wavelength Path (WP) networks: no wavelength conversion capability is provided in the switching nodes;        b) Virtual Wavelength Path (VWP) networks: every node is fully equipped with wavelength converters so that an incoming optical channel can always be converted on an idle output wavelength;        c) Partial Virtual Wavelength Path (PVWP) networks: only part of the nodes are equipped with wavelength converters.        
Two different traffic types may be offered to a WDM network:                a) static traffic: a known set of permanent connection requests is assigned a priori to the network, which must be able to satisfy all the requests together, starting from the idle network;        b) dynamic traffic: connection requests arrive at random instants to the nodes of the network and connections are semipermanent (i.e. temporary with long duration). Each connection is set up independently while other connections are active and network resources have already been allocated to other lightpaths. This situation is also referred in the known art as “provisioning”. In general, with provisioning there is no warranty that the network is able to find enough idle resources to satisfy a particular connection request: in this case, the connection is blocked.        
Static traffic is usually considered when a new network must be started up or an existing infrastructure must undergo a large scale reconfiguration or a physical topology upgrading. In these cases the network can be planned according to future traffic. Static planning can be so summarized: given a static traffic matrix, comprising a set of connection requests between pairs of source-destination nodes, find the optimum values of a set of network variables that minimizes a given cost function, under a set of constraints. The choice of variables, cost function and constraints greatly varies from case to case.
A known approach for static traffic planning consists in finding exact solutions, by formalizing the problem in order to obtain a mathematical representation based on matrices. Then, such problem can be solved as a linear or non-linear programming problem. This approach is described, for example, in B. Van Caenegan, W. Van Parys, F. De Turck, P. Demeester, “Dimensioning of survivable WDM networks”, IEEE Journal on Selected Area in Communications, 16(7), pag.1146-1157 (1998). Unfortunately in WDM networks many variables are integer and the exact solution can be obtained only with very complex and time-consuming algorithms (Integer Linear Programming, or ILP, problem).
Dynamic traffic can be considered during normal operation lifetime of the WDM network. In dynamic traffic conditions the optimal RFWA must be determined for every new lightpath requested in a given instant of time by a node pair of the network, keeping into account the network resources already allocated to other active connections. To perform the three functions of RFWA on the new connection request, a routing, a fiber and a wavelength assignment criterion has to be chosen: the main approach is to choose in a heuristic way among known simple algorithms.
Path routing is usually done by “Shortest Path” (SP) or “Least Loaded Routing” (LLR). The SP method tends to route the new connection along the shortest physical path linking the source node to the destination node. In defining the distance two metrics can be used: the first, referred as “Minimum Hop” (mH), evaluates the number of links (or hops) concatenated to form the path; the second, referred “Minimum Length” (mL), considers the total physical length of the path. The LLR method tends to route the lightpath avoiding links with very high loads (i.e. a small number of free wavelengths).
Typical wavelength and fiber assignment criteria are “Pack”, “Spread”, “First Fit” and “Random”. “Pack” and “Spread” consider the utilization of wavelengths on the network and define a priority order, promoting the most and the least used wavelength in the network, respectively. “First Fit” creates an arbitrary and preset priority order for wavelength selection which is kept unchanged throughout the whole network. In “Random” criterion, no priority order is predetermined and the wavelength assignment is made randomly.
Solving the static traffic planning with heuristic algorithms developed for dynamic traffic is known. For example, G. Maier, A. Pattavina, L. Roberti, T. Chich, “Static-Lightpath Design by Heuristic Methods in Multifiber WDM Networks”, Proceedings of OptiComm 2000 SPIE Conf, Dallas, Oct. 2000, pag.64-75, disclose an approach to WDM multifiber network design and optimization under static traffic aimed to minimize the number of fibers in the network. The heuristic optimization comprises an initial setup of all the demanded lightpaths and an iteration during which the network is progressively improved by rerouting lightpaths and consequently eliminating fibers with a high number of unused wavelengths. Static traffic is managed with the same techniques as dynamic traffic by suitably sorting the static connection demands and offering them in sequence to the network. The authors used a tool named “layered graph” (sometimes called wavelength graph) as a working auxiliary representation of the network state. This representation, often used for dynamic traffic analysis or for static optimization in monofiber networks, was used by the authors for a multifiber network optimization with static traffic. An example of a layered graph representing a simple network is shown in FIG. 2. The layered graph in a multifiber WDM network is built by replicating the physical network topology on a set of (W×F) parallel planes or graphs, where W is the number of wavelengths used in the network and F is the maximum number of fibers in a link: in FIG. 2, a network having two fibers per link (F=2) and two wavelengths per fiber (W=2) has been represented by a layered graph having four layers. Each of the n physical nodes of the network (A, B, D, E, F in FIG. 2) appears as a virtual image node in all the (W×F) planes. A further image of the node eventually represents its add-drop function. In FIG. 2, each of the image nodes belonging to the various layers has been labeled by the notation Nfw, where N is the label of the node, f is the label of the fiber, w is the label of the wavelength. Add-drop function of the nodes has been represented in FIG. 2 by the source-termination image nodes labeled by Ns,t, being outside of the various layers. Vertical (bidirectional) arcs between the image nodes represent OXC switching operations (fiber switching and wavelength conversion). If a physical node is equipped with wavelength converters its corresponding virtual nodes in different W planes are joined by vertical arcs; otherwise only planes having the same wavelength are vertically connected. FIG. 2 represents a network in which no wavelength conversion is provided. Associating a horizontal arc on the layered graph to a lighthop on the network implies both the adoption of the corresponding physical link of the topology and the choice of one particular fiber and one particular wavelength within it. In the Maier et al. article mentioned above, a single algorithm performs all these operations exploiting the layered graph. Suitable weights are associated to the nodes, to the vertical arcs and to the horizontal arcs, so the layered graph is transformed into a weighted graph. Then, a Dijkstra algorithm finds the connection path with the least total weight on the weighted graph, thus obtaining the RFWA of the lightpath. After an initial lightpath setup has been completed, all the empty fibers are pruned. Then an optimization iteration begins. An optimization counter k is defined and initially set to 1. Any “k-fiber”, that is a fiber containing only k occupied wavelengths and (W−k) unused wavelengths, is detected. The lightpaths routed on that k-fiber are considered sequentially. Each of them is de-allocated and allocated again with the general RFWA criteria chosen for the optimization. If a new allocation is not possible the old lightpaths are maintained. When rerouting of all the lightpaths on the selected fiber has been attempted, the procedure is repeated on all the other k-fibers of the network. Then all the empty fibers are pruned again, k is incremented and another iteration begins. The whole is repeated until k=(W−1). As recognized by the same authors, the disclosed tool does not provide protection lightpaths for the connection lightpaths found.
The use of the WDM technique on optical fibers allowed a progressive growing of the transmission capacity of the network, with very high bit rates and very high data traffic volumes on a limited number of optical paths. As a consequence, a failure occurring in a component of the network (for example a fiber cut or even a whole cable cut) becomes more and more critical, as a failure can result in a huge loss of information. Clearly, the most critical situation is represented by the failure of a whole node. A network is called “survivable” if it allows the re-routing of a connection involved in a failure event. Restore techniques currently used are the Protection and the Restoration.
With the Protection technique, spare resources are provided in the network, to be used in case of failure. Typically, a dedicated protection path is provided for any working path, to be used in case of failure on the working path. Such protection path is disjoint from the working path. With the Restoration technique, restore paths are dynamically allocated in case of failure. In Applicants' opinion, Restoration techniques require higher restore times, as they necessitate of complex signaling techniques between the nodes involved by the failure, and do not guarantee survivability, as the dynamic search of a restoration path may be unsuccessful.
Patent application EP 0969620, to Lucent Technologies Inc., discloses heuristic provisioning methods for a static set of connections on a given WDM optical network technology. A first class of solutions relates to provisioning in so-called primary networks, that is, networks that do not account for possible network failures. A second class of solutions adapts and extends the heuristic provisioning solutions used in primary networks for use in restorable networks. Heuristic methods disclosed in the '620 patent application are based on a so-called “two-step” algorithm, in which each selected connection is first removed from the network, then an admissible lightpath that has the minimum metric (or cost) is found via the Dijkstra shortest path algorithm, and finally the connection is rerouted on that lightpath.
In Applicants' opinion, the use of a two-step algorithm is not convenient, because it may fail to find solutions in some situations. Basically, a two-step algorithm consists in: a) identifying the shortest path (or the path giving the lower cost) between two nodes and associating to this shortest path a working lightpath in the network; b) removing such shortest path and finding a further shortest path between the same two nodes in the thus modified topology, and associating to this further shortest path a spare lightpath in the network. This approach can be applied in order to find pairs of paths on a network, for example pairs of working-spare paths. However, for example, FIG. 3a shows an example of a simple network topology where the two-step approach fails to find a suitable pair of paths from node A to node Z. Let the weight associated to any link be equal to 1 for all links but for AD and BE: let the weight of AD and BE be equal to 2. ABCZ is the shortest path between the nodes A and Z. FIG. 3b shows how the topology is modified by the first step of removing the shortest path ABCZ. According to FIG. 3b, no further path can be found from node A to node Z: thus, no pair of paths between A and Z could be found. On the contrary, FIG. 3c shows that the two disjoint paths ADCZ and ABEZ exist between nodes A and Z.
Applicants have faced the problem of providing a tool for static or dynamic traffic planning of a WDM optical network, such tool providing pairs of working-protection paths for one or more connection requests to be setup, in order to plan or provision a survivable network with dedicated protection. Heuristic algorithms different from the two-step algorithm were considered, in order to avoid time consuming and complex ILP algorithms, at the same time obtaining high reliability in finding the working-protection pairs of paths. In particular, in case of static traffic planning, Applicants have also faced the problem of minimizing the cost of the survivable network.
As disclosed in R. Bhandari's book “Survivable Networks—Algorithms for Diverse Routing”, Kluwer Academic Publishers, 1999, a heuristic one-step algorithm capable of determining shortest pairs of disjoint paths on a given topology, in a more reliable way with respect to the above described two-step algorithm, is the Bhandari algorithm, disclosed at chapter 3 of the same book. Bhandari algorithm for finding the edge-disjoint shortest pair of paths between a given pair of vertices is the following:    a. Select one of the two vertices as the source vertex and the second as the destination vertex, find the shortest path, for example using the modified Dijkstra algorithm.    b. Replace each edge of the shortest path by a single arc directed towards the source vertex.    c. Make the length (weight) of each of the above arcs negative.    d. Find the shortest path on the thus modified graph, for example by using the modified Dijkstra algorithm.    e. Transform to the original graph, and erase any interlacing edges of the two paths found. Group the remaining edges to obtain the shortest pair of edge-disjoint paths.
An application of this algorithm to the simple network topology already shown in FIGS. 3a-b-c is shown in FIGS. 4a-b-c. Let the weight associated to any link be equal to 1 for all links but for AD and BE: let the weight of AD and BE be equal to 2. FIG. 4a shows the graph after step a), after which the path ABCZ has been found as shortest path. FIG. 4b shows the graph after steps b)-c)-d), after which the shortest path ADCBEZ has been found on the modified graph. As it can be seen from a comparison between FIG. 4a and FIG. 4b the link BC is interlaced between the first and the second shortest path. FIG. 4c shows the pair of disjoint paths ADCZ and ABEZ found after erasing the common link BC and grouping the remaining links of the two shortest paths found at steps a) and d).
A similar algorithm allows the finding of the vertex-disjoint shortest pair of paths between a given pair of vertices:    a. For the given pair of vertices under consideration, find the shortest path, for example using the modified Dijkstra algorithm.    b. Replace each edge on the shortest path by an arc directed towards the destination vertex.    c. Split each vertex on the shortest path into two co-located sub-vertices joined by an arc of length (weight) zero. Direct this arc towards the destination vertex. Replace each external edge connected to a vertex on the shortest path by its two component arcs (of length or weight equal to the edge length or weight); let one arc terminate on one sub-vertex, and the other arc emanate from the other sub-vertex such that along with the zero-length arc a cycle results.    d. Reverse the direction of the arcs on the shortest path. Also make their lengths (or weights) negative.    f. Find the shortest path on the thus modified graph, for example by using the modified Dijkstra algorithm.    g. Remove the zero length (weight) arcs; coalesce the sub-vertices into their parent vertices. Replace the single arcs of the shortest path with their original edges (of positive length or weight). Remove interlacing edges of the two paths found above to obtain the shortest pair of paths.
Vertex-disjoint paths are also edge-disjoint paths, while the converse is not necessarily true.
Bhandari's book does not deal with WDM networks and discloses its algorithms as applied to a graph having a single layer.
Applicants have faced the problem of adapting the Bhandari algorithms for finding edge- or vertex-disjoint pairs of paths on a layered graph representing an optical network, in particular a multi-fiber WDM network. In this context, edge-disjoint paths on the layered graph correspond to link-disjoint paths on the network, and vertex-disjoint paths correspond to node-disjoint paths on the network. Applicants have understood that at least some of the steps of the Bhandari algorithms are not directly applicable to a graph comprising a plurality of layers representing an optical network: in such graph, in fact, the layers are correlated with each other, due to the fact that the image nodes and the horizontal arcs laying in each layer represent the same physical links and the same physical nodes in the network, respectively. This framework is further complicated by the fact that the network can have or not wavelength conversion capability. Applicants have understood that if the algorithms do not take into account the correlations between the layers (correlations which may be different case by case, for example in case of WP, VWP or PVWP network), one may find disjoint paths in the layered graph, but being actually not disjoint in the physical network.